package hot100.logos81To90;

/**
 * @author logos
 * date 2025/7/18 18:58
 * @version v1.0
 * @Package hot100.logos81To90
 */
public class logos89 {

    /**
     * 89. 分割等和子集
     * https://leetcode.cn/problems/partition-equal-subset-sum/submissions/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int x : nums) {
                sum += x;
            }
            if (sum % 2 != 0) {
                return false;
            }
            sum /= 2;
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            int s2 = 0;
            for (int x : nums) {
                s2 = Math.min(s2 + x, sum);
                for (int j = s2; j >= x; j--) {
                    dp[j] = dp[j] || dp[j - x];
                }
                if (dp[sum]) {
                    return true;
                }
            }
            return false;
        }
    }
}
